package problems

import (
	"bytes"
	"fmt"
	"math"
	"math/rand"
	"sort"
	"strconv"
	"strings"
)

// 401
// https://leetcode-cn.com/problems/binary-watch/
func ReadBinaryWatch(num int) []string {
	var res []string
	var hours = [4][]string{
		{`0`},
		{`1`, `2`, `4`, `8`},
		{`3`, `5`, `6`, `9`, `10`, `12`},
		{`7`, `11`},
	}
	var minutes = [6][]string{
		{`00`},
		{`01`, `02`, `04`, `08`, `16`, `32`},
		{`03`, `05`, `06`, `09`, `10`, `12`, `17`, `18`, `20`, `24`, `33`, `34`, `36`, `40`, `48`},
		{`07`, `11`, `13`, `14`, `19`, `21`, `22`, `25`, `26`, `28`, `35`, `37`, `38`, `41`, `42`, `44`, `49`, `50`, `52`, `56`},
		{`15`, `23`, `27`, `29`, `30`, `39`, `43`, `45`, `46`, `51`, `53`, `54`, `57`, `58`},
		{`31`, `47`, `55`, `59`},
	}
	for i := 0; i <= num; i++ {
		if i < 4 && num-i < 6 && len(hours[i]) > 0 && len(minutes[num-i]) > 0 {
			for _, hour := range hours[i] {
				for _, minute := range minutes[num-i] {
					res = append(res, hour+`:`+minute)
				}
			}
		}
	}
	return res
}

// 404
// https://leetcode-cn.com/problems/sum-of-left-leaves/
func SumOfLeftLeaves(root *TreeNode) int {
	var sum = 0
	var sumLeft func(root *TreeNode, isLeft bool)
	sumLeft = func(root *TreeNode, isLeft bool) {
		if root != nil {
			if isLeft && root.Left == nil && root.Right == nil {
				sum += root.Val
			} else {
				sumLeft(root.Left, true)
				sumLeft(root.Right, false)
			}
		}
	}
	sumLeft(root, false)
	return sum
}

// 405
// https://leetcode-cn.com/problems/convert-a-number-to-hexadecimal/
func ToHex(num int) string {
	if num == 0 {
		return `0`
	}
	sm := map[int]string{10: `a`, 11: `b`, 12: `c`, 13: `d`, 14: `e`, 15: `f`}
	res := ``
	negative, remainder := num < 0, 0
	if negative {
		num = math.MaxInt32 + (num + 1)
	}
	for num > 0 {
		num, remainder = num/16, num%16
		if len(res) == 7 && negative {
			remainder += 8
		}
		if v, ok := sm[remainder]; ok {
			res = v + res
		} else {
			res = strconv.Itoa(remainder) + res
		}
	}
	if negative && len(res) < 8 {
		res = fmt.Sprintf(`8%07s`, res)
	}
	return res
}

// 409
// https://leetcode-cn.com/problems/longest-palindrome/
func LongestPalindrome(s string) int {
	bm := make(map[rune]int)
	length, odd := 0, false
	for _, v := range s {
		if _, ok := bm[v]; !ok {
			bm[v] = 0
		}
		bm[v]++
	}
	for _, v := range bm {
		if v > 1 {
			length += v - v%2
		}
		if !odd {
			odd = v%2 != 0
		}
	}
	if odd {
		length++
	}
	return length
}

// 412
// https://leetcode-cn.com/problems/fizz-buzz/
func FizzBuzz(n int) []string {
	var res = make([]string, n)
	for i := 1; i <= n; i++ {
		if i%15 == 0 {
			res[i-1] = `FizzBuzz`
		} else if i%5 == 0 {
			res[i-1] = `Buzz`
		} else if i%3 == 0 {
			res[i-1] = `Fizz`
		} else {
			res[i-1] = fmt.Sprintf("%d", i)
		}
	}
	return res
}

// 414
// https://leetcode-cn.com/problems/third-maximum-number/
func ThirdMax(nums []int) int {
	var maxes = [3]int{-math.MaxInt64, -math.MaxInt64, -math.MaxInt64}
	for _, v := range nums {
		if v != maxes[0] && v != maxes[1] && v != maxes[2] {
			if v > maxes[2] {
				maxes[0], maxes[1], maxes[2] = maxes[1], maxes[2], v
			} else if v > maxes[1] {
				maxes[0], maxes[1] = maxes[1], v
			} else if v > maxes[0] {
				maxes[0] = v
			}
		}
	}
	if maxes[0] == -math.MaxInt64 {
		return maxes[2]
	}
	return maxes[0]
}

// 415
// https://leetcode-cn.com/problems/add-strings/
func DddStrings(num1 string, num2 string) string {
	if len(num1) > len(num2) {
		num1, num2 = num2, num1
	}
	var res = make([]byte, len(num2)+1)
	var s = false
	for i := 0; i < len(num2); i++ {
		var sum = num2[len(num2)-1-i] - 48
		if s {
			sum += 1
		}
		if i < len(num1) {
			sum += num1[len(num1)-1-i] - 48
		}
		s = false
		if sum > 9 {
			s = true
			sum -= 10
		}
		res[len(num2)-i] = sum + 48
	}
	if s {
		res[0] = 49
		return string(res)
	}
	return string(res[1:])
}

// 426
// https://leetcode-cn.com/problems/linked-list-random-node/
type ListSolution struct {
	list *ListNode
}

/** @param head The linked list's head.
  Note that the head is guaranteed to be not null, so it contains at least one node. */
func ListSolutionConstructor(head *ListNode) ListSolution {
	return ListSolution{list: head}
}

/** Returns a random node's value. */
func (s *ListSolution) GetRandom() int {
	var val, num = 0, 0
	var head = s.list
	for head != nil {
		num++
		if rand.Intn(num) == 0 {
			val = head.Val
		}
		head = head.Next
	}
	return val
}

// 429
// https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
func LevelOrder2(root *ChildNode) [][]int {
	var res [][]int
	var stack []*ChildNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		var num = len(stack)
		var subRes []int
		for _, v := range stack {
			subRes = append(subRes, v.Val)
			stack = append(stack, v.Children...)
		}
		res = append(res, subRes)
		stack = stack[num:]
	}
	return res
}

// 434
// https://leetcode-cn.com/problems/number-of-segments-in-a-string/
func CountSegments(s string) int {
	var count = 0
	var last = true
	for _, v := range s {
		if v != ' ' {
			if last {
				count++
			}
			last = false
		} else {
			last = true
		}
	}
	return count
}

// 429 TODO
// https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
type Codec struct {
}

func CodecConstructor() Codec {
	return Codec{}
}

func (c *Codec) Serialize(root *TreeNode) string {
	var buff bytes.Buffer
	var stack []*TreeNode
	if root != nil {
		stack = append(stack, root)
	}
	for len(stack) > 0 {
		var num = len(stack)
		var allNil = true
		for _, v := range stack {
			if v == nil {
				buff.WriteString(`*`)
				stack = append(stack, nil, nil)
			} else {
				buff.WriteString(strconv.Itoa(v.Val))
				stack = append(stack, v.Left, v.Right)
				if v.Left != nil || v.Right != nil {
					allNil = false
				}
			}
		}
		if allNil {
			break
		}
		stack = stack[num:]
	}
	return strings.TrimRight(buff.String(), `*`)
}

func (c *Codec) Deserialize(data string) *TreeNode {
	if len(data) == 0 {
		return nil
	}
	var stack = make([]*TreeNode, len(data))
	var negative = false
	var index, pIndex = 0, 0
	for _, v := range data {
		if string(v) == `*` {
			index++
		} else if string(v) == `-` {
			negative = true
		} else {
			var num, _ = strconv.Atoi(string(v))
			var node = &TreeNode{Val: num}
			if negative {
				node.Val = -node.Val
				negative = false
			}
			stack[index] = node
			if index > 0 {
				if index%2 == 1 {
					if stack[pIndex] != nil {
						stack[pIndex].Left = node
					}
				} else {
					if stack[pIndex] != nil {
						stack[pIndex].Right = node
					}
					pIndex++
				}
			}
			index++
		}
	}
	return stack[0]
}

// 437
// https://leetcode-cn.com/problems/path-sum-iii/
func PathSum(root *TreeNode, sum int) int {
	if root == nil {
		return 0
	}
	var num = findSum(root, sum)
	if root.Left != nil {
		num += PathSum(root.Left, sum)
	}
	if root.Right != nil {
		num += PathSum(root.Right, sum)
	}
	return num
}

func findSum(root *TreeNode, subSum int) int {
	var num = 0
	if root != nil {
		if root.Val == subSum {
			num++
		}
		if root.Left != nil {
			num += findSum(root.Left, subSum-root.Val)
		}
		if root.Right != nil {
			num += findSum(root.Right, subSum-root.Val)
		}
	}
	return num
}

// 441
// https://leetcode-cn.com/problems/arranging-coins/
func ArrangeCoins(n int) int {
	var num = 0
	for i := 1; (i+1)*i/2 <= n; i++ {
		num = i
	}
	return num
}

// 443
// https://leetcode-cn.com/problems/predict-the-winner/
func Compress(chars []byte) int {
	var slow, fast, num = 0, 0, 0
	var appendNum = func() {
		for _, v := range strconv.Itoa(num) {
			chars[slow] = byte(v)
			slow++
		}
	}

	for fast < len(chars) {
		if chars[slow] != chars[fast] {
			slow++
			if num > 1 {
				appendNum()
			}
			chars[slow], num = chars[fast], 0
		}
		fast++
		num++
	}
	slow++
	if slow < len(chars) && num > 1 {
		appendNum()
	}
	return slow
}

// 448
// https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/
func FindDisappearedNumbers(nums []int) []int {
	for _, v := range nums {
		if v > 0 && nums[v-1] > 0 {
			nums[v-1] = -nums[v-1]
		} else if v < 0 && nums[-v-1] > 0 {
			nums[-v-1] = -nums[-v-1]
		}
	}
	var res []int
	for k, v := range nums {
		if v > 0 {
			res = append(res, k+1)
		}
	}
	return res
}

// 453
// https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements/
func MinMoves(nums []int) int {
	var min, sum = 0, 0
	if len(nums) > 0 {
		min = nums[0]
	}
	for _, v := range nums {
		sum += v
		if min > v {
			min = v
		}
	}
	return sum - min*len(nums)
}

// 455
// https://leetcode-cn.com/problems/assign-cookies/
func FindContentChildren(g []int, s []int) int {
	sort.Ints(g)
	sort.Ints(s)
	var sIndex, count = 0, 0
	for _, v := range g {
		for i := sIndex; i < len(s); i++ {
			if s[i] >= v {
				count++
				sIndex = i + 1
				break
			}
		}
		if sIndex >= len(s) {
			break
		}
	}
	return count
}

// 456
// https://leetcode-cn.com/problems/132-pattern/
func Find132pattern(nums []int) bool {
	if len(nums) < 3 {
		return false
	}
	// 最小、ai、ak、搜寻范围下限，搜寻范围上限
	min, ai, ak, rangeMin, rangeMax := nums[0], nums[0], nums[0], nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] >= ak || (nums[i] < ai && nums[i] > min) {
			ai, ak = min, nums[i]
		}
		if ai < ak && (ai < rangeMin || ak > rangeMax) {
			for j := i + 1; j < len(nums); j++ {
				if ai < nums[j] && ak > nums[j] {
					return true
				}
			}
			if ai < rangeMin {
				rangeMin = ai
			}
			if rangeMax < ak {
				rangeMax = ak
			}
		}
		if nums[i] < min {
			min = nums[i]
		}
	}

	return false
}

// 459
// https://leetcode-cn.com/problems/repeated-substring-pattern/
func RepeatedSubstringPattern(s string) bool {
	var sub []byte
	for i := 0; i < len(s); i++ {
		if len(sub) == 0 {
			sub = append(sub, s[i])
		} else {
			if s[i] == sub[0] && len(s)%i == 0 {
				var equal = true
				for j := i; j < len(s); j += i {
					if string(sub) != s[j:j+i] {
						equal = false
					}
				}
				if equal {
					return true
				}
			}
			sub = append(sub, s[i])
		}
	}
	return false
}

// 461
// https://leetcode-cn.com/problems/hamming-distance/
func HammingDistance(x int, y int) int {
	return strings.Count(fmt.Sprintf("%b", x^y), `1`)
}

// 463
// https://leetcode-cn.com/problems/island-perimeter/
func IslandPerimeter(grid [][]int) int {
	var count, col = 0, 0
	for k, v := range grid {
		for kk, vv := range v {
			if vv == 1 {
				if k > 0 && grid[k-1][kk] == 1 {
					col++
				}
				if kk > 0 && grid[k][kk-1] == 1 {
					col++
				}
				count++
			}
		}
	}
	return count*4 - col*2
}

// 475
// https://leetcode-cn.com/problems/heaters/
func FindRadius(houses []int, heaters []int) int {
	sort.Ints(houses)
	sort.Ints(heaters)
	var index, radius = 0, 0.0
	for _, house := range houses {
		var preRadius = math.Abs(float64(heaters[index] - house))
		for index < len(heaters)-1 {
			var subRadius = math.Abs(float64(heaters[index+1] - house))
			if preRadius >= subRadius {
				index++
				preRadius = subRadius
			} else {
				break
			}
		}
		if preRadius > radius {
			radius = preRadius
		}
	}
	return int(radius)
}

// 476
// https://leetcode-cn.com/problems/number-complement/
func FindComplement(num int) int {
	var res = 0
	var pos uint = 0
	for num > 0 {
		if num%2 == 0 {
			res += 1 << pos
		}
		num /= 2
		pos++
	}
	return res
}

// 482
// https://leetcode-cn.com/problems/license-key-formatting/
func LicenseKeyFormatting(S string, K int) string {
	S = strings.Replace(strings.ToUpper(S), `-`, ``, -1)
	var res = []byte(S[:len(S)%K])
	for i := len(S) % K; i < len(S); i += K {
		if len(res) > 0 {
			res = append(res, '-')
		}
		res = append(res, []byte(S[i:i+K])...)
	}
	return string(res)
}

// 485
// https://leetcode-cn.com/problems/max-consecutive-ones/
func FindMaxConsecutiveOnes(nums []int) int {
	var max, curMax = 0, 0
	for _, v := range nums {
		if max < curMax {
			max = curMax
		}
		if v == 0 {
			curMax = 0
		} else {
			curMax++
		}
	}
	if max < curMax {
		max = curMax
	}
	return max
}

// 486
// https://leetcode-cn.com/problems/predict-the-winner/
func PredictTheWinner(nums []int) bool {
	if len(nums) <= 2 {
		return true
	}
	var seek func(int, int) (int, int)
	nm := make(map[string][2]int) // 先取，后取
	seek = func(start, end int) (int, int) {
		if start == end {
			return nums[start], 0
		}
		if start+1 == end {
			if nums[start] > nums[end] {
				return nums[start], nums[end]
			}
			return nums[end], nums[start]
		}
		key := strconv.Itoa(start) + `-` + strconv.Itoa(end)
		if _, ok := nm[key]; !ok {
			leftA, leftB := seek(start+1, end)
			rightA, rightB := seek(start, end-1)
			if nums[start]+leftB-leftA > nums[end]+rightB-rightA {
				nm[key] = [2]int{nums[start] + leftB, leftA}
			} else {
				nm[key] = [2]int{nums[end] + rightB, rightA}
			}
		}
		return nm[key][0], nm[key][1]
	}

	a, b := seek(0, len(nums)-1)

	return a >= b
}

// 492
// https://leetcode-cn.com/problems/construct-the-rectangle/
func ConstructRectangle(area int) []int {
	var sqr = int(math.Sqrt(float64(area)))
	for area%sqr != 0 {
		sqr--
	}
	return []int{area / sqr, sqr}
}

// 496
// https://leetcode-cn.com/problems/next-greater-element-i/
func NextGreaterElement(nums1 []int, nums2 []int) []int {
	var res []int
	for k, v := range nums1 {
		var found bool
		for _, vv := range nums2 {
			if vv == v {
				found = true
			}
			if found && vv > v {
				res = append(res, vv)
				break
			}
		}
		if k == len(res) {
			res = append(res, -1)
		}
	}
	return res
}

// 500
// https://leetcode-cn.com/problems/keyboard-row/
func FindWords(words []string) []string {
	var wordsPosition = map[byte]uint8{
		65: 1,
		66: 2,
		67: 2,
		68: 1,
		69: 0,
		70: 1,
		71: 1,
		72: 1,
		73: 0,
		74: 1,
		75: 1,
		76: 1,
		77: 2,
		78: 2,
		79: 0,
		80: 0,
		81: 0,
		82: 0,
		83: 1,
		84: 0,
		85: 0,
		86: 2,
		87: 0,
		88: 2,
		89: 0,
		90: 2,
	}
	var res []string
	for _, v := range words {
		var line uint8 = 0
		for kk, vv := range v {
			if vv > 90 {
				vv -= 32
			}
			if kk == 0 {
				line = wordsPosition[byte(vv)]
			} else {
				if line != wordsPosition[byte(vv)] {
					goto END
				}
			}

		}
		res = append(res, v)
	END:
	}
	return res
}
